package 二叉搜索树;

public class BinarySearchTree {

    static class TreeNode {
        public int key;
        public TreeNode left;
        public TreeNode right;

        TreeNode(int key) {
            this.key = key;
        }
    }

    public TreeNode root;

    /**
     * 插入一个元素
     * @param key
     */
    public boolean insert(int key) {
        TreeNode node = new TreeNode(key);
        if(root == null){
            root = node;
            return true;
        }
        TreeNode cur = root;
        TreeNode tmp = root;
        while (cur != null){
            tmp = cur;
            if (cur.key < key){
                cur = cur.right;
            }else if (cur.key > key){
                cur = cur.left;
            }else {
                return false;
            }
        }
        if (tmp.key > key){
            tmp.left = node;
        }else {
            tmp.right = node;
        }
        return true;
    }

    //查找key是否存在
    public TreeNode search(int key) {
      TreeNode cur = root;
      while (cur != null){
          if (cur.key < key){
              cur = cur.right;
          }else if (cur.key > key){
              cur = cur.left;
          }else {
              return cur;
          }
      }
      return null;
    }

    //删除key的值
    public boolean remove(int key) {
        TreeNode cur = root;
        TreeNode trige = root;
        while (cur != null){
            trige = cur;
            if (cur.key < key){
                cur = trige.right;
            }else if (cur.key > key){
                cur = trige.left;
            }else {
                if (cur.left == null){
                    if (cur == root){
                        root = cur.right;
                    }else if (cur == trige.left){
                        trige.left = cur.right;
                    }else {
                        trige.right = cur.right;
                    }
                }else if (cur.right == null){
                    if (cur == root){
                        root = cur.left;
                    }else if (cur == trige.left){
                        trige.left = cur.left;
                    }else {
                        trige.right = cur.left;
                    }
                }else {
                    TreeNode preant = cur;
                    trige = cur.right;
                    while (trige.left != null){
                        preant = trige;
                        trige = trige.left;
                    }
                    cur.key = trige.key;
                    if(preant.left == trige){
                        preant.left = trige.right;
                    }else {
                        preant.right = trige.right;
                    }
                }
                return true;
            }
        }
        return false;
    }
    void inorder(TreeNode root){
        if (root == null){
            return;
        }
        inorder(root.left);
        System.out.print(root.key+" ");
        inorder(root.right);
    }
}